<div>
	Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов </div>

Добрынин Вячеслав Юрьевич, Абрамович Роман Константинович , Платонов Алексей Владимирович

doi:10.17586/2226-1494-2025-25-1-61-67

2025 , ТОМ 25, НОМЕР 1 ( январь-февраль )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2025-25-1-61-67

УДК 004.89

Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов

Добрынин В.Ю., Абрамович Р.К., Платонов А.В.

Читать статью полностью

Язык статьи - английский

Ссылка для цитирования:

Добрынин В.Ю., Абрамович Р.К., Платонов А.В. Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 1. С. 61–67 (на англ. яз.). doi: 10.17586/2226-1494-2025-25-1-61-67

Аннотация

Введение. Современные поисковые системы используют двухэтапную архитектуру для эффективного и качественного поиска по большим объемам данных. На первом этапе применяются простые и быстрые алгоритмы, такие как BM25, а на втором — более точные, но ресурсоемкие методы, например глубокие нейронные сети. Несмотря на то, что такой подход показывает хорошие результаты, он фундаментально ограничен по качеству из-за проблемы несовпадения словарей, что присуще простым алгоритмам первого этапа. Метод. Для решения проблемы ограничений качества поиска, в настоящей работе предлагается алгоритм построения инвертированного индекса с использованием векторных представлений. Представленный подход объединяет преимущества обоих этапов: эффективность инвертированного индекса и высокое качество поиска при использовании векторных моделей. Предложено создание векторного индекса, сохраняющего различные семантические значения токенов словаря. Для каждого токена определяются документы, в которых он используется, после чего его контекстуализированные эмбеддинги кластеризуются. Центроиды полученных кластеров представляют различные семантические значения токенов. Таким образом, формируется расширенный словарь, который применяется для построения инвертированного индекса. При построении индекса вычисляются оценки близости между каждым семантическим значением токена и документами, что затем используется в процессе поиска. Это позволяет сократить количество вычислений для оценки близости в режиме реального времени. Поиск по инвертированному индексу требует нахождения ключей в векторном индексе, что позволяет решить проблему несовпадения словарей. Основные результаты. Работа алгоритма продемонстрирована на задаче поиска в наборе данных SciFact. Показано, что предлагаемый метод обеспечивает высокое качество поиска при низких требованиях к объему памяти. Обсуждение. Разработанный алгоритм демонстрирует высокое качество поиска, при этом он поддерживает компактный векторный индекс, размер которого остается неизменным и определяется исключительно размерами словаря. Основным недостатком алгоритма является необходимость использования глубокой нейронной сети для генерации векторных представлений запроса в процессе поиска, что замедляет этот этап. Поиск путей для решения данной проблемы и сокращения времени поиска представляет собой направление дальнейших исследований.

Ключевые слова: инвертированный индекс, проблема несоответствия словарей, нейронные сети, векторные представления, кластеризация

Список литературы

Khattab O., Zaharia M. ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT // Proc. of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 2020. P. 39–48. https://doi.org/10.1145/3397271.3401075
Zamani H., Dehghani M., Croft W.B., Learned-Miller E., Kamps J. From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing // Proc. of the 27th ACM International Conference on Information and Knowledge Management. 2018. P. 497–506. https://doi.org/10.1145/3269206.3271800
Bai Y., Li X., Wang G., Zhang C., Shang L., Xu J., Wang Z., Wang F., Liu Q. SparTerm: Learning term-based sparse representation for fast text retrieval // arXiv. 2020. arXiv:2010.00768. https://doi.org/10.48550/arXiv.2010.00768
Devlin J., Chang M.W., Lee K., Toutanova K. BERT: Pre-training of deep bidirectional transformers for language understanding // arXiv. 2018. arXiv:1810.04805v2. https://doi.org/10.48550/arXiv.1810.04805
Formal T., Piwowarski B., Clinchant S. SPLADE: Sparse lexical and expansion model for first stage ranking // Proc. of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2021. P. 2288–2292. https://doi.org/10.1145/3404835.3463098
Santhanam K., Khattab O., Saad-Falcon J., Potts C., Zaharia M. ColBERTv2: Effective and efficient retrieval via lightweight late interaction // Proc. of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022. P. 3715–3734. https://doi.org/10.18653/v1/2022.naacl-main.272
Johnson J., Douze M., Jégou H. Billion-scale similarity search with GPUs // IEEE Transactions on Big Data. 2021. V. 7. N 3. P. 535–547. https://doi.org/10.1109/tbdata.2019.2921572
Jégou H., Douze M., Schmid C. Product quantization for nearest neighbor search // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2011. V. 33. N 1. P. 117–128. https://doi.org/10.1109/tpami.2010.57
Kong W., Dudek J.M., Li C., Zhang M., Bendersky M. SparseEmbed: Learning sparse lexical representations with contextual embeddings for retrieval // Proc. of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2023. P. 2399–2403. https://doi.org/10.1145/3539618.3592065
Tiancheng Z., Lu X., Lee K. SPARTA: Efficient Open-Domain Question Answering via Sparse Transformer Matching Retrieval // Proc. of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021. P. 565–575. https://doi.org/10.18653/v1/2021.naacl-main.47
Dobrynin V., Abramovich R., Platonov A. Building a full-text search index using ”Transformer” neural network // Proc. of the 2023 IEEE 17th International Conference on Application of Information and Communication Technologies (AICT). 2023. P. 1–5. https://doi.org/10.1109/aict59525.2023.10313200
Malkov Y.A., Yashunin D.A. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2020. V. 42. N 4. P. 824–836. https://doi.org/10.1109/tpami.2018.2889473
Arthur D., Vassilvitskii S. k-means++: the advantages of careful seeding // Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms Mathematics. 2007. P. 1027–1035.
Bajaj P., Campos D., Craswell N., Deng L., Gao J., Liu X., Majumder R., McNamara A., Mitra B., Nguyen T., Rosenberg M., Song X., Stoica A, Tiwary S., Wang T. MS MARCO: a human generated MAchine Reading COmprehension dataset // arXiv. 2016. arXiv:1611.09268. https://doi.org/10.48550/arXiv.1611.09268
Thakur N., Nils R., Rücklé A., Srivastava A., Gurevych I. BEIR: A heterogenous benchmark for zero-shot evaluation of information retrieval models // arXiv. 2021. arXiv:2104.08663. https://doi.org/10.48550/arXiv.2104.08663

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License